﻿#define  _CRT_SECURE_NO_WARNINGS 1
# include<stdio.h>

// [题目链接](https://www.nowcoder.com/practice/41c399fdb6004b31a6cbb047c641ed8a)

//环形链表的约瑟夫问题
//编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数，报到 m 的人离开。
//
//下一个人继续从 1 开始报数。
//
//n - 1 轮结束以后，只剩下一个人，问最后留下的这个人编号是多少？
//
//数据范围： 1≤𝑛, 𝑚≤100001≤* n*, * m* ≤10000
//
//进阶：空间复杂度 𝑂(1)* O* (1)，时间复杂度 𝑂(𝑛)* O* (*n*)

struct ListNode 
{
    int val;
    struct ListNode* next;
};

typedef struct ListNode ListNode;

ListNode* BuyNode(int x)
{
    ListNode* node = (ListNode*)malloc(sizeof(ListNode));
    if (node == NULL)
    {
        perror("malloc");
        exit(1);
    }
    node->val = x;
    node->next = NULL;

    return node;
}

ListNode* CreateCircleList(int n)
{
    // 创建n个节点
    // 先创建第一个节点出来
    ListNode* phead = BuyNode(1);
    ListNode* ptail = phead;
    // 通过for循环 去尾插剩下要插入的n-1个节点
    for (int i = 2; i <= n; i++)
    {
        ListNode* node = BuyNode(i); // 创建节点
        // 将节点尾插到链表当中
        ptail->next = node;
        ptail = ptail->next;
    }
    // 走到这里创建了一个n个节点的链表 但是还不是环形链表
    // 让最后一个节点的next指针指向phead 也就是第一个节点
    ptail->next = phead; // 链表成环

    return ptail; // 返回最后一个节点才能找到第一个节点和第一个节点前面的节点
}

int ysf(int n, int m)
{
    // 根据n创造一个环形链表，n个节点
    ListNode* prev = CreateCircleList(n);
    ListNode* pcur = prev->next; // pcur指向链表的第一个节点

    // 这个时候开始约瑟夫删除节点 根据给的m来删除节点
    while (pcur->next != pcur) // 当剩下一个节点的时候才能退出循环 也就是pcur的next指针指向自己的时候
    {
        // 遍历链表 当pcur往后走了m - 1步之后  删除pcur指向的节点
        for (int i = 0; i < m - 1; i++)
        {
            prev = pcur; // prev是用来指向pcur的前一个节点的
            pcur = pcur->next;
        }

        // 此时的pcur指向的节点 要进行删除
        prev->next = pcur->next;// 让prev指向pcur的下一个节点
        free(pcur); // 删除pcur指向的节点
        pcur = prev->next; // 让pcur指向下一次要走m步的起点

    }
    // 这个时候就剩下一个节点  就是幸存者
    ListNode* ret = pcur->val;
    free(pcur); // 释放掉自己申请的动态内存空间
    pcur = NULL;
    return ret;
}

// int ysf函数还可以有另外一个思路
int ysf(int n, int m)
{
    // 根据n创造一个环形链表，n个节点
    ListNode* prev = CreateCircleList(n);
    ListNode* pcur = prev->next; // pcur指向链表的第一个节点

    int count = 1;
    // 这个时候开始约瑟夫删除节点 根据给的m来删除节点
    while (pcur->next != pcur) //当剩下一个节点的时候才能退出循环 也就是pcur的next指针指向自己的时候
    {
        // 要让pcur向后走到count = m才行能删除pcur指向的节点  
        // 分为不删除节点的情况和不删除的情况
        if (count == m) // 删除
        {
            // 删除pcur指向的节点
            prev->next = pcur->next;
            free(pcur);
            pcur = prev->next;
            count = 1; // 置为1 
        }
        else // 不删除
        {
            // 此时不删除pcur 指向的节点 
            // 让pcur往后走就行
            prev = pcur; // prev是用来指向pcur的前一个节点的
            pcur = pcur->next;// pcur往后走
            count++; // 让count统计此时pcur指向的的节点是否要删除
        }
    }
    // 这个时候就剩下一个节点  就是幸存者
    ListNode* ret = pcur->val;
    free(pcur); // 释放掉自己申请的动态内存空间
    pcur = NULL;
    return ret;
}
